package com.nav.util;

public class MedianTree<T extends Comparable<T>> {
	T median;
	Tree<T> l = new Tree<T>(), r = new Tree<T>();
	public void add(T e) {
		if(median == null) {
			T rm = r.getMin();
			if(rm != null && e.compareTo(rm) < 0) {
				l.add(e);
				median = l.removeMax();
			} else {
				r.add(e);
				median = r.removeMin();
			}
		} else {
			if(e.compareTo(median) < 0) {
				l.add(e);
				r.add(median);
			} else {
				l.add(median);
				r.add(e);
			}
			median = null;
		}
	}
	public boolean remove(T e) {
		if(median == null) {
			if(l.remove(e)) {
				median = r.removeMin();
				return true;
			} else if(r.remove(e)) {
				median = l.removeMax();
				return true;
			}
		} else {
			if(e.compareTo(median) < 0) {
				if(l.remove(e)) {
					l.add(median);
					median = null;
					return true;
				}
			} else if(e.compareTo(median) > 0) {
				if(r.remove(e)) {
					r.add(median);
					median = null;
					return true;
				}
			} else {
				median = null;
				return true;
			}
		}
		return false;
	}
	public String toString() {
		return "{" + median + ", " + l + ", " + r + "}";
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
	}
}
